vector翻译为向量，但是这里使用“变长数组”的叫法更容易理解，也即“长度根据需要而自动改变的数组”。在考试题中，有时会碰到只用普通数组会超内存的情况，这种情况使用vector会让问题的解决便捷许多。另外， vector还可以用来以邻接表的方式储存图，这对无法使用邻接矩阵的题目(结点数太多)、又害怕使用指针实现邻接表的读者是非常友好的写法也非常简洁。

需要的头文件:

需要的其他东西:

vector的定义的格式:

上面这个定义其实相当于是一维数组name[ SIZE ]，只不过其长度可以根据需要进行变化, 比较节省空间，说通俗了就是"边长数组"。

和一维数组一样,这里的typename 可以是任何基本类型，例如: int 、double 、char、结构体等,也可以是STL标准容器, 例如 vector 、set、queue等。需要注意的是，如果typename也是一个STL容器，定义的时候要记得在 >> 符号之间加上空格, 因为一些使用C++ 11之前标准的编译器会把它视为移位操作,导致编译错误。 例子:

如果typename 是vector,就是下面这样定义:

可以很容易联想到二维数组的定义,即其中一维是一个数组的数组。那么二维vector数组也是一样的， 即Arrayname[]中的每一个元素都是vector。 初学者可以把二维vector 数组当作两个维都可变长的二维数组理解。

定义vector数组的方法:

这样Arrayname[0] ~ Arrayname[ arraySize - 1 ] 中的每一个元素都是一个vector容器。

vector一般有两种访问方式 , 通过下标访问或通过迭代器访问。 一、通过下标访问 和访问普通的数组是一样的，对一个定义为vector vi 的容器来说 直接访问vi[ index ] 即可(如vi[0]、vi[1])。当然这里的下标是从0 到 vi.size()-1。 访问这个范围外的元素可能会出错。 二、通过迭代器访问 迭代器( iterator ) 可以理解为一种类似指针的东西,其定义是:

这样it 就是一个vector:: iterator型的变量,其中 typename 就是定义vector时填写的类型。 下面是typename为int和 double 类型的举例:

这样就得到了迭代器it,并且可以通过 *it 来访问vector里的元素 从这里可以看出 vi [ i ] 和 * ( vi.begin() + i )是等价的。 上面中的begin()函数的作用为 : 取 a的首元素地址。 end()函数是取a的尾元素地址的下一个地址。end()作为迭代器末尾标志，不存储任何元素。

除此之外，迭代器还实现了两种自加操作: ++it 和 it++ 于是有了另一种遍历vector中元素的写法: 需要注意的是: vector的迭代器不支持 it < v1.end() 写法，因此循环条件只能用 it != vi.end()

最后需要指出,在常用STL容器中，只有在vector和string中，才允许使用vi.begin()+3这种迭代器加上整数的写法。

(1) push_back() 顾名思义，push_back(x)就是在vector后面添加一个元素x,时间复杂度为O(1)。 (2) pop_back() pop_back()用以删除vector的尾元素，时间复杂度为O(1)。 注意: pop_back()函数是没有参数的 (3) size() size()用来获得vector中元素的个数，时间复杂度为O(1)。size()返回的是unsigned类型, 不过一般来说用%d不会出很大问题，这一点对所有STL容器都是一样的。 例子:

(4) clear() clear()用来清空vector中的所有元素，时间复杂度为O(N),其中N为vector中元素的个数。

(5) insert() inesrt(it,x)用来向vector的任意迭代器it处插入一个元素x,时间复杂度O(N)。 (6)erase() erase()有两种方法: 删除单个元素、删除一个区间内的所有元素。时间复杂度都为O(N)。 ①删除单个元素 erase(it) 即删除迭代器为it处的元素。

②删除一个区间内的所有元素 erase(first,last)即删除 [ first , last) 内的所有元素。 上面的说法可以直到，如果要删除这个vector内的所有元素， 正确的写法应该是v1.erase( v1.begin() , v1.end() )。 这正如前面说过，v1.end()就是尾元素地址的下一个地址。 当然，更方便的清空vector的方法是使用v1.clear()。

(1)存储数据

(2)用邻接表存储图 使用vector实现邻接表可以让一些对指针不太熟悉的读者有一个比较方便的写法。